The present invention concerns an interleaver, an encoding device, a permutation method, a encoding method, a decoding device and method and systems using them.
It applies equally well to the encoding of data representing a physical quantity, to the encoding of data in the form of codes capable of modulating a physical quantity, to the decoding of data modulated signals, and to the decoding of data representing physical quantities. These data can, for example, represent images, sounds, computer data, electrical quantities, or stored data.
The invention finds an application in the field of serial or hybrid convolutional codes. When the latter are used for implementing an iterative decoding, these codes are greatly improved when their encoders contain a permutation device. In this case, they are usually referred to as xe2x80x9cturbocodesxe2x80x9d and the corresponding iterative decoder is referred to as a xe2x80x9cturbodecoderxe2x80x9d.
Serial turbocodes relate to the serial concatenation of two convolutional encoders separated by an interleaver. The decoding method is iterative. Hybrid turbocodes have an architecture which is both serial and parallel.
The second encoder of a serial turbo-encoder is always systematic and recursive.
On these subjects, documents which serve as references are:
the articles by Messrs. C. BERROU, A. GLAVIEUX and P. THITIMAJSHIMA entitled xe2x80x9cNear Shannon limit error-correcting coding and decoding:turbocodesxe2x80x9d published with the reports of the xe2x80x9cICC""93xe2x80x9d conference, 1993, pages 1064 to 1070, and by Messrs. C. BERROU and A. GLAVIEUX entitled xe2x80x9cNear Optimum error-correcting coding and decoding: turbo-codesxe2x80x9d published by IEEE Transactions on Communication, Volume COM-44, pages 1261 to 1271, in October 1996, with regard to parallel turbo-encoding,
the articles xe2x80x9cSerial concatenation of interleaved codes: Performance analysis, design and iterative decodingxe2x80x9d, Benedetto, Montorsi, (Univ. Politecnico di Torino, Italy), Divsalar, Pollara, (JPL, USA), TDA progress report, 42-126, August 1996; and xe2x80x9cHybrid concatenated codes and iterative decodingxe2x80x9d, Divsalar, Pollara, (JPL, USA), TDA progress report, 42-130, August 1997, with regard to serial or hybrid turbo-encoding.
However, the formation of the permutation devices is far from being completely mastered. For example, this device uses square or rectangular matrices which are written into one row after another and read from one column after another. These matrices are generally very large, for example 256xc3x97256 in size.
Let, for example, the permutation device with k=65536=256xc3x97256, mentioned above, be considered, and let a predetermined error probability equal to 10xe2x88x925 be chosen for simulating the performance of a turbocode using this device. Consequently, the mean number of errors over the binary values per 256xc3x97256 block will be close to 1, but it will not be known whether each item of binary information has the same error probability. This error probability could be quite high for binary values having an xe2x80x9cunfortunatexe2x80x9d position in the permutation device and this probability could be much lower for more xe2x80x9cfortunatexe2x80x9d positions.
One possible way for remedying this situation is to carry out a harmonious and joint design of the permutation device and the convolutional encoders in order to guarantee a reasonable uniformity of the error rate over the binary values after decoding, according to the position of the binary information in the permutation device.
Another problem concerns the lack of algebraic tools for specifying the permutation devices. It would be useful to have available means making it possible to specify a selection of permutation devices having performances representative of the set of all the permutation devices.
In the remainder of the description, for representing a sequence u, the form u=(u0, u1, . . . , ukxe2x88x921), and the associated polynomial form:
u(x)=u0x0+u1x1+ . . . +ukxe2x88x921xkxe2x88x921,
are used indiscriminately,
and a sequence formed by permutation of the binary data of the sequence u will be denoted by u*.
The polynomial divisions used are of the type of division according to ascending powers, well known to persons skilled in the art. They use modulo 2 arithmetic.
The simultaneous return to the zero state of the convolutional encoders used in a turbo-encoder is a classic problem.
The present invention intends to propose families of interleavers which guarantee the return to zero of the convolutional encoders used as components in a serial or hybrid turbo-encoder.
To that end, according to a first of its aspects, the present invention relates to an encoding method, characterised in that:
1/ it takes into account:
two predetermined integers M1 and M2, equal to or greater than 1,
a number K, greater than or equal to 1, of sequences ai(i=1, . . . ,K) of binary data representing a physical quantity, each sequence ai having:
a polynomial representation ai(x) which is a multiple of a predetermined polynomial gi(x), and
a number of binary data items equal to the product of any integer number M and the integer N0, the smallest integer such that the polynomial xN0+1 is divisible by each of the polynomials gi(x);
2/ it has an operation of convolutional encoding of the sequences ai into K+M2 so-called xe2x80x9cintermediatexe2x80x9d sequences di,
3/ it has a first production operation for a number (K+M2)*M1 of so-called xe2x80x9cpermutedxe2x80x9d sequencesxe2x80x9d, dij*, (i=1, . . . ,K+M2; j=1, . . . ,M1), each sequence dij*
being obtained by a permutation of the corresponding sequence di, the said permutation being, in a representation where the binary data items of each sequence di are written, row by row, Into a table with N0 columns and M rows, the result of any number of so-called elementary permutations, each of which:
either has the property of transforming the cyclic code of length N0 and with generator polynomial gi(x) into an equivalent cyclic code with generator polynomial gij(x) which may be equal to gi(x), and acts by permutation on the N0 columns of the table representing di,
or is any permutation of the symbols of a column of the said table; and
having, in consequence, a polynomial representation dij*(x) which is equal to a polynomial product cij(x)gij(x),
4/ it has a second production operation for M1 redundant sequences, the polynomial representation of which is equal to xcexa3fij(x)cij(x), for i=1, . . . , K+M2 and j=1, . . . ,M1, each polynomial fij(x) being a polynomial of degree at most equal to the degree of the polynomial gij(x) with the same indices i and j.
Above, there have been introduced, in a representation where the binary data items of the sequence a are arranged in a table of N0 columns and M rows, the successions of permutations taken from the set of permutations having, on the one hand, the automorphisms of the binary cyclic code of length N0 and with generator polynomial g(x), permuting between them the columns of the table and, on the other hand, the permutations working solely on data of one and the same column and permuting between them at least two of the said data items.
The inventors have, discovered that all these successions of permutations, and only these, guarantee that, for any polynomial a(x) whose division by g(x) leaves a null remainder, the permuted polynomial a*(x) has the same property.
For a study of the conditions governing the choice of the gij""s, the reader can refer to page 234 of the book by Mrs F. J. MAC WILLIAMS and Mr N. J. A. SLOANE xe2x80x9cThe theory or error-correcting codesxe2x80x9d published by the publisher North-Holland in 1977, the seventh impression of which took place in 1992).
All the choices described in the present invention include the interleavers described in the two articles mentioned above. Thus the performances expressed in terms of error rate as a function of the signal/noise ratio can be improved without increasing the complexity of the turbo-encoder nor that of the turbodecoder.
According to a second aspect, the present invention relates to an encoding method, characterised in that:
1/ it takes into account:
two predetermined integers M1 and M2, equal to or greater than 1,
a number K, greater than or equal to 1, of sequences ai (i=1, . . . ,K) of binary data representing a physical quantity, each sequence ai having:
a polynomial representation ai(x) which is a multiple of a predetermined polynomial gi(x) with no multiple polynomial factors, and
a number of binary data items equal to the product of any odd integer number M and the integer N0, the smallest integer such that the polynomial xN0+1 is divisible by each of the polynomials gi(x);
2/ it has an operation of convolutional encoding of the sequences ai into K+M2 so-called xe2x80x9cintermediatexe2x80x9d sequences di,
3/ it has a first production operation for a number (K+M2)*M1 of so-called xe2x80x9cpermutedxe2x80x9d sequences, dij*, (i=1, . . . ,K; j=1, . . . ,M1), each sequence dij* having a polynomial representation equal to dij*(x)=di(xeij) modulo (xn+1), where
n is the product of the number M and the integer N0,
eij is a number relatively prime with n
cij is the quotient of dij*(x) divided by gij(x),
the polynomial gij(x) is the generator polynomial of the smallest cyclic code of length N0 containing the polynomial gi(xeij) modulo (xN0+1),
at least one permuted sequence aij* being different from the corresponding sequence ai*,
4/ it has a second production operation for M1 redundant sequences, the polynomial representation of which is equal to xcexa3fij(x)cij(x), for i=1, . . . ,K+M2 and j=1, . . . ,M1, each polynomial fij(x) being a predetermined polynomial of degree at most equal to the degree of the polynomial gij(x) with the same indices i and j.
By virtue of these provisions, the majority of columns in the table can be moved by permutation, on the one hand, and, within this restricted choice, the minimum distance of the turbocode is more easily analysable and therefore can be optimized, on the other hand.
This second aspect of the invention has the same advantages as the first aspect.
According to particular characteristics, during the first production operation, all the values of the exponents eij having the same value of the index j are identical.
By virtue of these provisions, the encoding method to which the present invention relates makes it possible to perform all the interleavings with j fixed in the same manner. It is therefore simple to carry out.
By virtue of these provisions, the polynomials gij are all identical.
According to particular characteristics, during the first production operation, all the values of the exponents eij are equal to a power of 2.
According to particular characteristics, the encoding method to which the present invention relates, as briefly described above, has an operation of transmitting, on the one hand, the sequences ai, and, on the other hand, a subset of the data of the other sequences.
By virtue of these provisions, the efficiency of the method is increased.
According to other particular characteristics, the encoding method to which the present invention relates has an addition operation during which additional so-called xe2x80x9cpaddingxe2x80x9d information items are added to sequences ui of information data items in order to form the sequences ai guaranteeing the divisibility of the polynomial representation of the resulting sequence ai by the polynomial gi(x).
Thus, the divisibility of each sequence ai by the sequence gi is guaranteed by a pre-encoding operation.
According to other particular characteristics, during the operation of convolutional encoding of the sequences ai into K+M2 so-called xe2x80x9cintermediatexe2x80x9d sequences di, an operation of multiplying the polynomial representation of each sequence ai by the polynomial gi(x) is performed.
Thus, it is the convolutional encoding operation which guarantees that the polynomial representations of the sequences to be interleaved corresponding to the sequences ai are respectively multiples of the polynomials gi(x).
According to particular characteristics, the encoding method to which the present invention relates, as briefly described above, also has:
5/ a third production operation for a number K*M3 of so-called xe2x80x9cpermutedxe2x80x9d sequences, axe2x80x2ij*, (i=1, . . . ,K; j=1, . . . ,M3), each sequence axe2x80x2ij*
being obtained by a permutation of the corresponding sequence ai, the said permutation being, in a representation where the binary data items of each sequence ai are written, row by row, into a table with N0 columns and M rows, the result of any number of so-called elementary permutations, each of which:
either has the property of transforming the cyclic code of length N0 and with generator polynomial gxe2x80x2i(x) into an equivalent cyclic code with generator polynomial gxe2x80x2ij(x) which may be equal to gxe2x80x2i(x), and acts by permutation on the N0 columns of the table representing ai,
or is any permutation of the symbols of a column of the said table; and
having, in consequence, a polynomial representation axe2x80x2ij*(x) which is equal to a polynomial product bxe2x80x2ij(x)gxe2x80x2ij(x),
6/ a fourth production operation for M3 redundant sequences, the polynomial representation of which is equal to xcexa3fxe2x80x2ij(x)bxe2x80x2ij(x), for j=1, . . . ,M3, each polynomial fxe2x80x2ij(x) being a polynomial of degree at most equal to the degree of the polynomial gxe2x80x2ij(x) with the same indices i and j.
According to particular characteristics, the encoding method to which the present invention relates, as briefly described above:
5/ has a third production operation for a number K*M3 of so-called xe2x80x9cpermutedxe2x80x9d sequences, axe2x80x2ij*, (i=1, . . . ,K; j=1, . . . ,M3), each sequence axe2x80x2ij* having a polynomial representation equal to axe2x80x2ij*(x)=ai(xexe2x80x2ij) modulo (xn+1), where
n is the product of the number M and the integer N0,
exe2x80x2ij is a number relatively prime with n
bxe2x80x2ij is the quotient of axe2x80x2ij*(x) divided by gxe2x80x2ij(x),
the polynomial gxe2x80x2ij(x) is the generator polynomial of the smallest cyclic code of length N0 containing the polynomial gxe2x80x2i(xexe2x80x2ij) modulo (xN0+1),
6/ it has a fourth production operation for M3 redundant sequences, the polynomial representation of which is equal to xcexa3fxe2x80x2ij(x)bxe2x80x2ij(x), for j=1, . . . ,M3, each polynomial fxe2x80x2ij(x) being a predetermined polynomial of degree at most equal to the degree of the polynomial gxe2x80x2ij(x) with the same indices i and j.
By virtue of each of these provisions, the hybrid turbo-encoders enjoy the advantages of the present invention, as described above.
According to a third aspect, the present invention relates to an encoding device, characterised in that it has a processing means adapted to:
1/ take into account:
two predetermined integers M1 and M2, equal to or greater than 1,
a number K, greater than or equal to 1, of sequences ai (i=1, . . . ,K) of binary data representing a physical quantity, each sequence ai having:
a polynomial representation ai(x) which is a multiple of a predetermined polynomial gi(x), and
a number of binary data items equal to the product of any integer number M and the integer N0, the smallest integer such that the polynomial xN0+1 is divisible by each of the polynomials gi(x);
2/ perform a convolutional encoding of the sequences ai into K+M2 so-called xe2x80x9cintermediatexe2x80x9d sequences di,
3/ perform a first production operation for a number (K+M2)*M1 of so-called xe2x80x9cpermutedxe2x80x9d sequences, dij*, (i=1, . . . ,K+M2; j=1, . . . ,M1), each sequence dij*
being obtained by a permutation of the corresponding sequence di, the said permutation being, in a representation where the binary data items of each sequence di are written, row by row, into a table with N0 columns and M rows, the result of any number of so-called elementary permutations, each of which:
either has the property of transforming the cyclic code of length N0 and with generator polynomial gi(x) into an equivalent cyclic code with generator polynomial gij(x) which may be equal to gi(x), and acts by permutation on the N0 columns of the table representing di,
or is any permutation of the symbols of a column of the said table; and
having, in consequence, a polynomial representation dij*(x) which is equal to a polynomial product cij(x)gij(x),
at least one permuted sequence aij* being different from the corresponding sequence ai*,
4/ perform a second production operation for M1 redundant sequences, the polynomial representation of which is equal to xcexa3fij(x)cij(x), for i=1, . . . , K+M2 and j=1, . . . ,M1, each polynomial fij(x) being a polynomial of degree at most equal to the degree of the polynomial gij(x) with the same indices i and j.
According to a fourth aspect, the present invention relates to an encoding device, characterised in that it has a processing means adapted to:
1/take into account:
two predetermined integers M1 and M2, equal to or greater than 1,
a number K, greater than or equal to 1, of sequences ai (i=1, . . . ,K) of binary data representing a physical quantity, each sequence ai having:
a polynomial representation ai(x) which is a multiple of a predetermined polynomial gi(x) with no multiple polynomial factors, and
a number of binary data items equal to the product of any odd integer number M and the integer N0, the smallest integer such that the polynomial xN0+1 is divisible by each of the polynomials gi(x);
2/ perform an operation of convolutional encoding of the sequences ai into K+M2 so-called xe2x80x9cintermediatexe2x80x9d sequences di,
3/ perform a first production operation for a number (K+M2)*M1 of so-called xe2x80x9cpermutedxe2x80x9d sequences, dij*, (i=1, . . . ,K; j=1, . . . ,M1), each sequence dij* having a polynomial representation equal to dij*(x)=di(xeij) modulo (xn+1), where
n is the product of the number M and the integer N0,
eij is a number relatively prime with n
cij is the quotient of dij*(x) divided by gij(x),
the polynomial gij(x) is the generator polynomial of the smallest cyclic code of length N0 containing the polynomial gi(xeij) modulo (xN0+1),
at least one permuted sequence aij* being different from the corresponding sequence ai*,
4/ perform a second production operation for M1 redundant sequences, the polynomial representation of which is equal to xcexa3fij(x)cij(x), for i=1, . . . ,K+M2 and j=1, . . . ,M1, each polynomial fij(x) being a predetermined polynomial of degree at most equal to the degree of the polynomial gij(x) with the same indices i and j.
According to a fifth aspect, the present invention relates to a decoding method, characterised in that:
1/ it takes into account:
predetermined integers M1 and M2 equal to or greater than 1,
a number K, greater than or equal to 1, of sequences ai (i=1, . . . ,K) of data representing a physical quantity, each sequence ai having:
a polynomial representation ai(x) which is a multiple of a predetermined polynomial gi(x), and
a number of binary data items equal to the product of any integer number M and the integer N0, the smallest integer such that the polynomial xN0+1 is divisible by each of the polynomials gi(x);
2/ It has an operation of receiving signals representing:
K+M1+M2 sequences ai of n symbols aij;
which implements M1 permutation operations, at least one of which is not identity, each permutation being, in a representation where the binary data items of each sequence are written, row by row, into a table with N0 columns and M rows, the result of any number of so-called elementary permutations, each of which:
either has the property of transforming the cyclic code of length N0 and with generator polynomial gi(x) into an equivalent cyclic code with generator polynomial gij(x) which may be equal to gi(x), and acts by permutation on the N0 columns of the representative table,
or is any permutation of the symbols of a column of the said table;
3/ it has an operation of serial turbodecoding of K sequences of symbols using the divider polynomials gij(x).
According to a sixth aspect, the present invention relates to a decoding device, characterised in that:
1/ it has a processing means adapted to take into account:
predetermined integers M1 and M2 equal to or greater than 1,
a number K, greater than or equal to 1, of sequences ai (i=1, . . . ,K) of data representing a physical quantity, each sequence ai having:
a polynomial representation ai(x) which is a multiple of a predetermined polynomial gi(x), and
a number of binary data items equal to the product of any integer number M and the integer N0, the smallest integer such that the polynomial xN0+1 is divisible by each of the polynomials gi(x);
2/ it has a receiving means adapted to receive signals representing:
K+M1+M2 sequences ai of n symbols aij;
which implements M1 permutation operations, at least one of which is not identity, each permutation being, in a representation where the binary data items of each sequence are written, row by row, into a table with N0 columns and M rows, the result of any number of so-called xe2x80x9celementaryxe2x80x9d permutations, each of which:
either has the property of transforming the cyclic code of length N0 and with generator polynomial gi(x) into an equivalent cyclic code with generator polynomial gij(x) which may be equal to gi(x), and acts by permutation on the N0 columns of the representative table,
or is any permutation of the symbols of a column of the said table;
3/ the processing means is adapted to perform an operation of serial turbodecoding of K sequences of symbols using the divider polynomials gij(x).
The invention also relates to:
an information storage means readable by a computer or a microprocessor storing instructions of a computer program, characterised in that it allows the implementation of the method of the invention as briefly described above, and
an information storage means which is removable, partially or totally, and readable by a computer or a microprocessor storing instructions of a computer program, characterised in that it allows the implementation of the method of the invention as briefly described above.
The invention also relates to:
a device for processing signals representing speech, which has a device as briefly described above,
a data transmission device having a transmitter adapted to implement a packet transmission protocol, which has a device as briefly described above,
a data transmission device having a transmitter adapted to implement the ATM (Asynchronous Transfer Mode) packet transmission protocol, which has a device as briefly described above,
a data transmission device having a transmitter adapted to implement the packet transmission protocol, on an ETHERNET (registered trade mark) type network,
a network station, which has a device as briefly described above,
a data transmission device having a transmitter transmitting on a wireless channel, which has a device as briefly described above, and
a device for processing sequences of signals representing at most one thousand binary data items, which has a device as briefly described above.
These encoding and decoding devices, these encoding and decoding methods and these signal processing, data transmission and sequence processing devices and this network having the same particular characteristics and the same advantages as the encoding method as briefly described above, these particular characteristics and these advantages are not repeated here.